A flash storage system typically includes a flash controller and a flash memory. The flash controller manages data stored in the flash memory and transfers data between the flash memory and a host computer. In many flash storage systems, the flash controller includes an error correction circuit for detecting and correcting data bit errors in data stored in the flash memory. In this way, the error correction circuit improves reliability of the flash storage system.
One type of error correction circuit often employed in a flash storage controller is a Bose-Chaudhuri-Hochquenghem (BCH) error correction circuit. The BCH error correction circuit includes a syndrome generator, a locator polynomial generator, a search module, and a correction module. The syndrome generator generates syndromes based on a data unit, and the locator polynomial generator generates a locator polynomial based on the syndromes. The locator polynomial has a number of roots equal to the degree of the locator polynomial. Moreover, each of the roots may be used to locate a data bit error in the data unit. The search module locates data bit errors in the data unit by analyzing the roots of the locator polynomial. The correction module corrects the data bit errors in the data unit. In this way, the BCH correction circuit corrects a number of data bit errors equal to the degree of the locator polynomial generated by the BCH correction circuit. Moreover, the BCH error correction circuit has an error correction capacity defined by the maximum degree of a locator polynomial the locator polynomial generator is capable of generating.
Although BCH error correction circuits have been successfully employed to correct data bit errors in flash storage systems, in some applications the number of data bit errors occurring in a data unit stored in a flash storage system exceeds the error correction capacity of the BCH error correction circuit in the flash storage system.